Back خوارزمية شور Arabic Алгоритъм на Питър Шор Bulgarian Algorisme de Shor Catalan Shors algoritme Danish Shor-Algorithmus German Shor's algorithm English Algoritmo de Shor Spanish الگوریتم شور Persian Shorin algoritmi Finnish Algorithme de Shor French

Shori algoritm

Shori algoritm on kvantarvutusalgoritm täisarvu algtegurite leidmiseks. Selle töötas välja Ameerika matemaatik Peter Shor aastal 1994.[1][2] See on üks väheseid teadaolevaid kvantarvutuse algoritme, millel on veenvad potentsiaalsed rakendused ja tugevad tõendid superpolünoomse kiirenduse kohta võrreldes parimate tuntud klassikaliste (mittekvantiliste) algoritmidega.[3] Teisalt nõuab piisavalt suurte arvude tegurdamine palju rohkem kvantbitte, kui on lähitulevikus saadaval.[4] Teine probleem on see, et kvantahelates tekkiv müra võib tulemusi rikkuda,[5] mis nõuab kvantvigade korrigeerimiseks täiendavaid kvantbitte.

Shor pakkus välja mitmeid sarnaseid algoritme tegurdamisülesande, diskreetse logaritmi ülesande ja perioodi leidmise ülesande lahendamiseks. Shori algoritm viitab tavaliselt tegurdamisalgoritmile, kuid võib tähendada ka ükskõik millist neist kolmest algoritmist. Diskreetse logaritmi algoritm ja tegurdamisalgoritm on perioodi leidmise algoritmi juhtumid ning kõik kolm on varjatud alamgrupi probleemi juhtumid.[6]

Kvantarvutis töötab Shori algoritm täisarvu tegurdamiseks polünoomses ajas, mis tähendab, et kuluv aeg on polünoomne suhtes.[6] See kasutab kiire korrutamise korral kvantväravaid suurusjärgus ,[7] või isegi , kasutades asümptootiliselt kõige kiiremat praegu teadaolevat korrutamisalgoritmi, mille töötasid välja Harvey ja Van Der Hoven,[8] seega näidates, et täisarvu tegurdamise probleemi saab kvantarvutis tõhusalt lahendada ning see kuulub keerukusklassi BQP. See on oluliselt kiirem kui kõige tõhusam teadaolev klassikaline tegurdamisalgoritm, üldine arvuvälja sõel, mis töötab subeksponentsiaalses ajas: .[9]

  1. ↑ Goldwasser, Shafi; IEEE Computer Society, toim-d (1994). Proceedings / 35th Annual Symposium on Foundations of Computer Science, November 20 - 22, 1994, Santa Fe, New Mexico. Los Alamitos, Calif.: IEEE Computer Society Press. ISBN 978-0-8186-6580-6.
  2. ↑ Shor, Peter W. (10. oktoober 1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing (inglise). 26 (5): 1484–1509. DOI:10.1137/S0097539795293172. ISSN 0097-5397.
  3. ↑ Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum computation and quantum information (10th anniversary edition trükk). Cambridge: Cambridge university press. ISBN 978-1-107-00217-3.
  4. ↑ Gidney, Craig; Ekerå, Martin (15. aprill 2021). "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits". Quantum (inglise). 5: 433. DOI:10.22331/q-2021-04-15-433. ISSN 2521-327X.
  5. ↑ Cai, Jin-Yi (juuli 2024). "Shor's algorithm does not factor large integers in the presence of noise". Science China Information Sciences (inglise). 67 (7). DOI:10.1007/s11432-023-3961-3. ISSN 1674-733X.
  6. ↑ 6,0 6,1 "Pseudo-polynomial time", Wikipedia (inglise), 4. detsember 2023, vaadatud 24. oktoobril 2024
  7. ↑ Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1. august 1996). "Efficient networks for quantum factoring". Physical Review A (inglise). 54 (2): 1034–1063. DOI:10.1103/PhysRevA.54.1034. ISSN 1050-2947.
  8. ↑ Harvey, David; van der Hoeven, Joris (1. märts 2021). "Integer multiplication in time $O(n\mathrm{log}\, n)$". Annals of Mathematics. 193 (2). DOI:10.4007/annals.2021.193.2.4. ISSN 0003-486X.
  9. ↑ Weisstein, Eric W. "Number Field Sieve". mathworld.wolfram.com (inglise). Vaadatud 25. oktoobril 2024.

Developed by StudentB